package problem;

public class P_0057 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int first_cover_index = -1;
        int last_cover_index = intervals.length;
        for(int i=0; i<intervals.length; i++){
            if(newInterval[0] >= intervals[i][0] && newInterval[1] <= intervals[i][1]){
                return intervals;
            }
            if(intervals[i][0]<= newInterval[0] && intervals[i][1] >= newInterval[0]){
                first_cover_index = i;     // 第一个重叠，且部分重叠
            }
            if(intervals[i][0]<= newInterval[1] && intervals[i][1] >= newInterval[1]){
                last_cover_index = i;
                break;
            }
        }
        if(intervals.length==0){
            int[][] res = new int[1][2];
            res[0][0] = newInterval[0];
            res[0][1] = newInterval[1];
            return res;
        }
        if(newInterval[1] < intervals[0][0]){
            int[][] res = new int[intervals.length+1][2];
            res[0][0] = newInterval[0];
            res[0][1] = newInterval[1];
            for(int i=1; i<=res.length-1;i++){
                res[i][0] = intervals[i-1][0];
                res[i][1] = intervals[i-1][1];
            }
            return res;
        } else if(newInterval[0] > intervals[intervals.length-1][1]){
            int[][] res = new int[intervals.length+1][2];
            res[intervals.length][0] = newInterval[0];
            res[intervals.length][1] = newInterval[1];
            for(int i=0; i<res.length-1;i++){
                res[i][0] = intervals[i][0];
                res[i][1] = intervals[i][1];
            }
            return res;
        } else {
            if(first_cover_index == last_cover_index){
                return intervals;
            }else if(first_cover_index < 0){
                intervals[last_cover_index][0] = newInterval[0];
                return intervals;
            }else if(last_cover_index >= intervals.length){
                intervals[first_cover_index][1] = newInterval[1];
                return intervals;
            } else{
                int num = intervals.length - (last_cover_index - first_cover_index);
                newInterval[0] = intervals[first_cover_index][0];
                newInterval[1] = intervals[last_cover_index][1];
                int[][] res = new int[num][2];
                for(int i=0; i<first_cover_index; i++){
                    res[i][0] = intervals[i][0];
                    res[i][1] = intervals[i][1];
                }
                res[first_cover_index][0] = newInterval[0];
                res[first_cover_index][1] = newInterval[1];
                int i= first_cover_index + 1;
                for(int j=last_cover_index+1; j<intervals.length; j++){
                    res[i][0] = intervals[j][0];
                    res[i][1] = intervals[j][1];
                    i++;
                }
                return res;
            }

        }
    }


    public static void main(String[] args){
        P_0057 solution = new P_0057();
        //int[][] arr = {{1,2},{3,5},{6,7},{8,10},{12,16}};
        int[][] arr = {{2, 3}, {5, 7}};
        int[] interval = {0, 6};
        solution.insert(arr, interval);
    }
}
